/*
 * KDTree.h
 *
 *  Created on: Apr 20, 2011
 *      Author: alki
 */

#ifndef KDTREE_H_
#define KDTREE_H_

#include "Objekt.h"
#include "../math/Vektor.h"
#include "../math/Gerade.h"
#include <vector>

using namespace std;

/**
 * Klasse KDTree: repräsentiert den KD-Baum der Szene
 */
class KDTree {
public:
	KDTree();
	virtual ~KDTree();

	/**
	 * Objekte einfügen
	 */
	void insert(const Objekt* objekt);

	/**
	 * KD-Baum aufteilen
	 */
	void split(unsigned int max);

	/**
	 * DEBUG: Testausgabe
	 */
	void out() const;
	void out(int ebenen) const;
	void out(int ebene,int cursor) const;
	void leafesout() const;

	bool operator<(const KDTree *tree) const;

	void resize();

	/**
	 * überpruft auf Schnitt mit Gerade
	 */
	float Intersects(const Gerade &ray) const;

	bool hasNodes() const { return m_node1!=NULL; }
	KDTree *getNode(unsigned int i) const { if(i==1) return m_node1; return m_node2; }

	void getObjekte(vector<const Objekt*> *objekte) const;

private:
	/**
	 * Nodes
	 */
	KDTree *m_node1;
	KDTree *m_node2;

	/**
	 * Objekte, die der KD-Baum (an der aktuellen Stelle) beinhaltet
	 */
	vector<const Objekt*> m_objekte;

	/**
	 * Eckpunkte
	 */
	Vektor m_min;
	Vektor m_max;

	/**
	 * Überprüft auf Schnitt mit Objekt
	 */
	bool Intersects(const Objekt *objekt) const;
	bool ObjInTree(const Objekt *objekt) const;
	Vektor getMid() const { return (m_max+m_min)/2; }
	void clear() { m_objekte.clear(); }
};

#endif /* KDTREE_H_ */
